Blar i Bergen Open Research Archive på forfatter "Sæther, Sigve Hortemo"
-
Choice of parameter for DP-based FPT algorithms: four case studies
Sæther, Sigve Hortemo (Doctoral thesis, 2015-09-07)This thesis studies dynamic programming algorithms and structural parameters used when solving computationally hard problems. In particular, we look at algorithms that make use of structural decompositions to overcome ... -
Maximum matching width: New characterizations and a fast algorithm for dominating set
Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne (Peer reviewed; Journal article, 2015)We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ...